#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

int n;


LL k(LL a,LL b,LL mod)
{
	LL sum=1;
	while(b){
		if(b&1) sum=sum*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return sum%mod;
}


int main()
{
	scanf("%d",&n);
	
	while(n--){
		LL a,p;
		scanf("%lld%lld",&a,&p);
		if(a%p) printf("%lld\n",k(a,p-2,p));
		else  printf("impossible\n");
	}
	
	return 0;
}
